package com.sicheng.lc.周赛.分类.dp.线性;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/13 23:08
 */
public class 有效的括号字符串 {
    //https://leetcode.cn/problems/valid-parenthesis-string/
    public boolean checkValidString(String s) {
        if (s.charAt(0) == ')')
            return false;
        boolean[][] dp = new boolean[s.length()][s.length() / 2 + 10];
        dp[0][2] = true;
        dp[0][1] = s.charAt(0) == '*';
        for (int i = 1; i < s.length(); i++) {
            for (int j = 1; j <= s.length() / 2 + 5; j++) {
                if (s.charAt(i) == '*')
                    dp[i][j] |= dp[i - 1][j] | dp[i - 1][j - 1] | dp[i - 1][j + 1];
                else if (s.charAt(i) == '(')
                    dp[i][j] |= dp[i - 1][j - 1];
                else
                    dp[i][j] |= dp[i - 1][j + 1];
            }
        }

        return dp[s.length() - 1][1];
    }

    // fixme
    public boolean stack(String s) {
        if (s.charAt(0) == ')')
            return false;
        int sum = 0;
        int lazy = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '*') {
                lazy++;
                continue;
            }
            sum += s.charAt(i) == '(' ? 1 : -1;
            if (sum < 0 && lazy == 0)
                return false;
            else if (sum < 0 && lazy > 0) {
                sum++;
                lazy--;
            }

        }

        return lazy >= sum;
    }


    public static void main(String[] args) {
        有效的括号字符串 s = new 有效的括号字符串();
        System.out.println(s.stack("("));
//        System.out.println(s.checkValidString("(((((*(()((((*((**(((()()*)()()()*((((**)())*)*)))))))(())(()))())((*()()(((()((()*(())*(()**)()(())"));
    }
}
